package Leetcode.动态规划;

import edu.emory.mathcs.backport.java.util.Arrays;

import java.util.Scanner;
public class matrixChain {
    static int N=100;
    static int []p=new int[N];//记录矩阵的行和列，第i个矩阵的行数存储在数组的第i-1个位置，列数存储在数组的第i个位置。
    static int [][]m=new int[N][N];//表示AiAi+1A...Aj矩阵连乘的最优值
    static int [][]s=new int[N][N];//存放各个子问题的最优决策
    static int n;//多少个数组
    static void matrixChain(){
        int i,j,r,k;
        //初始化数组，使m[][],s[][]对角线上的元素为0
        for( i=0;i<N;i++){
            for (j=0;j<N;j++){
                if(i==j){
                    m[i][j]=0;
                    s[i][j]=0;
                }
            }
        }
        for(r=2;r<=n;r++){//r为问题规模，处理不同规模的子问题
            for(i=1;i<=n-r+1;i++){
                j=i+r-1;
                m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//决策为k=i的乘法次数
                s[i][j]=i;//子问题的最优策略是i
                for(k=i+1;k<j;k++){//对从i+1到j的所有决策，求最优值
                    int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(t<m[i][j])
                    {
                        m[i][j]=t;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
    static void print(int i,int j){
        if(i==j){
            System.out.print("A["+i+"]");
            return;
        }
        System.out.print("(");
        print(i,s[i][j]);
        print(s[i][j]+1,j);
        System.out.print(")");
    }

    /**
     * 此方法用来求解矩阵连乘的最小数乘次数
     *
     * @param p 传入的要连乘的矩阵的维数信息的数组
     * @return String型的矩阵的最小数层次数信息
     */
    public static String matrixChain(int[] p) {

        // n表示矩阵的数量减1，因为最后一个元素是矩阵链中最后一个矩阵的列数
        int n = p.length - 1;
        // m用于存储链乘的最小代价
        int[][] m = new int[n + 1][n + 1];
        // s用于存储分割点，用于后续的打印最优括号化方案
        int[][] s = new int[n + 1][n + 1];

        // 初始化对角线元素为0，因为单个矩阵的链乘代价为0
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;
        }

        // r表示当前计算的链长（子问题规模）
        for (int r = 2; r <= n; r++) {
            // i表示链的前边界，n-r+1是最后一个r链的前边界
            for (int i = 1; i <= n - r + 1; i++) {
                // j表示链的后边界
                int j = i + r - 1;

                // 初始化m[i][j]，假设链ij划分为A(i) * (A[i+1:j])
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
                // 记录分割点
                s[i][j] = i;

                // 尝试所有可能的分割点k，寻找最小代价
                for (int k = i + 1; k < j; k++) {
                    // 计算链ij划分为(A[i:k]) * (A[k+1:j])的代价
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    // 如果找到更小的代价，则更新m[i][j]和s[i][j]
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
        System.out.println("m:");
        for (int i = 1; i < n; i++) {
            System.out.println(Arrays.toString(m[i]));
        }
        System.out.println("s:");
        for (int i = 1; i < n; i++) {
            System.out.println(Arrays.toString(s[i]));
        }

        // 构建最终答案字符串，包含最小乘法次数
        String answer = "此矩阵连乘所需的最小次数为：" + m[1][n];

        // 打印最优括号化方案
        System.out.println(matrixTraceBack(1, n, s));
        return answer;
    }
    private static String matrixTraceBack(int i, int j, int[][] s) {
        if (i == j) {
            return "A" + i;
        }

        // 生成左侧子表达式
        String left = matrixTraceBack(i, s[i][j], s);

        // 生成右侧子表达式
        String right = matrixTraceBack(s[i][j] + 1, j, s);

        // 构造当前层的表达式
        return "(" + left + right + ")";
    }

    // 辅助函数，用于计算链乘的最小乘法次数
    private static int matrixChainRecursive(int[] p, int i, int j,int[][] s) {
        // 如果只有一个矩阵，不需要乘法
        if (i == j) {
            return 0;
        }

        int minCost = Integer.MAX_VALUE;

        // 尝试所有可能的分割点k，并计算最小乘法次数
        for (int k = i; k < j; k++) {
            int cost =  matrixChainRecursive(p, i, k,s) +
                        matrixChainRecursive(p, k + 1, j,s) +
                        p[i - 1] * p[k] * p[j];
            if (cost < minCost) {
                minCost = cost;
                s[i][j] = k;
            }
        }

        return minCost;
    }

    // 递归
    public static String matrixChain_2(int[] p) {
        int n = p.length - 1;
        int[][] s = new int[n + 1][n + 1];
        int minCost = matrixChainRecursive(p, 1, n, s);
        // 打印最优括号化方案
        System.out.println(matrixTraceBack(1, n, s));
        return "此矩阵连乘所需的最小次数为：" + minCost;
    }
    /*
    m:
    [0, 0, 36, 84, 96, 124]
    [0, 0, 0, 72, 84, 126]
    [0, 0, 0, 0, 48, 132]
    [0, 0, 0, 0, 0, 56]
    s:
    [0, 0, 1, 2, 1, 4]
    [0, 0, 0, 2, 2, 4]
    [0, 0, 0, 0, 3, 4]
    [0, 0, 0, 0, 0, 4]
     */
    public static void main(String[] args) {
        int[] arr = {2, 3, 6, 4, 2, 7};
        System.out.println(matrixChain(arr));
        System.out.println(matrixChain_2(arr));
        /*Scanner sc=new Scanner(System.in);
        System.out.println("请输入矩阵的个数n个数：");
        n=sc.nextInt();
        int i;
        System.out.println("请一次输入每个矩阵的行数和最后一个矩阵的列数：");
        for (i=0;i<=n;i++){
            p[i]=sc.nextInt();
        }
        matrixChain();
        print(1,n);
        System.out.println();
        System.out.println("最小计算量的值为："+m[1][n]);*/
    }
}
